import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-02
 * Time: 17:09
 */
public class BigHeap {
    public int [] elem;
    public int usedSize;
    public BigHeap(int [] arr){
        this.elem= Arrays.copyOf(arr,arr.length);
        this.usedSize =arr.length;
    }


    /**
     * 向下调整算法
     */
    public void shiftDown(int parent,int end){
        int left=parent*2+1;
        //没有孩子
        if(left> end){
            return;
        }

        while(left<= end){
            int maxi=left;
            int right=left+1;
            //右孩子大于左孩子
            if(right<= end && elem[right]>elem[left]){
                maxi=right;
            }
            //孩子大于双亲就交换
            if(elem[maxi]>elem[parent]){
                int temp=elem[maxi];
                elem[maxi]=elem[parent];
                elem[parent]=temp;
                parent=maxi;
                left=parent*2+1;
            }else {
                //否则就是交换完了
                break;
            }
        }

    }
    public void creatBigHeap(){
        int end= this.usedSize -1;
        //从倒数第一个非叶子节点开始调整
        for (int i = (end-1)/2; i >=0 ; i--) {
            shiftDown(i,end);
        }
    }


    public void shiftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[parent]<elem[child]){
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }
    public void offer(int val){
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++]=val;
        shiftUp(usedSize -1);
    }

    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int temp=elem[0];
        elem[0]=elem[usedSize -1];
        elem[usedSize -1]=temp;
        //必须先减1再向下调整
        usedSize = usedSize -1;
        shiftDown(0,usedSize-1);
        return temp;
    }

    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        return elem[0];
    }

    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            int temp=elem[0];
            elem[0]=elem[end];
            elem[end]=temp;
            //一定要先end--再调整
            end--;
            shiftDown(0,end);
        }
    }

    public boolean isEmpty(){
        return usedSize ==0;
    }
    public boolean isFull(){
        return elem.length== usedSize;
    }
}
